SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Calendar queue</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Calendar queue</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>A <b>calendar queue</b> (CQ) is a <a href="Priority_queue" title="Priority queue">priority queue</a> (queue in which every element has associated priority and the dequeue operation removes the highest priority element). It is analogous to desk calendar, which is used by humans for ordering future events by date. <a href="Discrete_event_simulation" class="mw-redirect" title="Discrete event simulation">Discrete event simulations</a> require a future event list (FEL) structure that sorts pending events according to their time. Such simulators require a good and efficient data structure as time spent on queue management can be significant. The calendar queue (with optimum bucket size) can approach O(1) average performance. Calendar queues are closely related to <a href="Bucket_queue" title="Bucket queue">bucket queues</a> but differ from them in how they are searched and in being dynamically resized.

</p>

<div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2></div>

<p>Theoretically, like a bucket queue, a calendar queue consists of an array of <a href="Linked_list" title="Linked list">linked lists</a>. Sometimes each index in the array is also referred to as a bucket. The bucket has specified width and its linked list holds events whose timestamp maps to that bucket. A desk calendar has 365 buckets for each day with a width of one day. Each array element contains one <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a> that is the head of the corresponding linked list. If the array name is "month" then month[11] is a pointer to the list of events scheduled for the 12th month of the year (the vector index starts from 0). The complete calendar thus consists of an array of 12 pointers and a collection of up to 12 linked lists. In calendar queue, enqueue (addition in a <a href="Queue_(abstract_data_type)" title="Queue (abstract data type)">queue</a>) and dequeue (deleting from a queue) of events in FEL is based on event time.

</p><p>Let the calendar queue with <i>n</i> buckets with <i>w</i> width. Then enqueue of an event with time <i>t</i> operates on bucket <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {t}{w}}\mod n}">

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {t}{w}}\mod n}</annotation>

</semantics>

</math></span><img src="./a0862fbe1d99417a7ed160bfea7b9c2b1eb2b025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:12.157ex; height:5.176ex;" alt="{\displaystyle {\frac {t}{w}}\mod n}" loading="lazy"></span> . And more than two events scheduled in the bucket according to the increased timestamp. To dequeue events from the calendar queue, it keeps track of current year and day. Then it searches for the earliest event within that bucket and dequeue it. (In contrast, a bucket queue would merely return any element from the first nonempty bucket, without determining which element in that bucket is earliest.)

</p>

<div class="mw-heading mw-heading2"><h2 id="Calendar_queue_resize_operation">Calendar queue resize operation</h2></div>

<p>If the number of events in the queue is much smaller or much larger than the number of buckets, it will not function efficiently. The solution is to allow the number of buckets to correspondingly grow and shrink as the queue grows and shrinks. To simplify the resize operation, the <i>Nb</i> (number of buckets) in a CQ is often chosen to be the power of two, i.e., <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Nb=2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Nb=2^{n}}</annotation>

</semantics>

</math></span><img src="./fd9483b568df60b4fe0a2dc1bed266bba48720c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.541ex; height:2.343ex;" alt="{\displaystyle Nb=2^{n}}" loading="lazy"></span>;↵

</p><p>The number of buckets is doubled or halved each time the <i>Ne</i> (number of events) exceeds 2<i>Nb</i> or decreases below <i>Nb</i>/2 respectively. When <i>Nb</i> is resized, the new width <i>w</i> has to be calculated as well. The new <i>w</i> that is adopted will be estimated by sampling the average inter-event time gap from the first few hundred events starting at the current bucket position. Thereafter, a new Calendar queue is created and all the events in the old calendar will be recopied over.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBrown1988" class="citation cs2">Brown, R. (October 1988), "Calendar queues: a fast <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation>

</semantics>

</math></span><img src="./e66384bc40452c5452f33563fe0e27e803b0cc21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}" loading="lazy"></span> priority queue implementation for the simulation event set problem", <i><a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>, <b>31</b> (10): <span class="nowrap">1220–</span>1227, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F63039.63045">10.1145/63039.63045</a></span>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:32086497">32086497</a></cite></li>

<li><cite id="CITEREFEricksonLadnerLaMarca2000" class="citation cs2">Erickson, K. Bruce; Ladner, Richard E.; LaMarca, Anthony (2000), "Optimizing static calendar queues", <i>ACM Transactions on Modeling and Computer Simulation</i>, <b>10</b> (3): <span class="nowrap">179–</span>214, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F361026.361028">10.1145/361026.361028</a></span></cite></li>

<li><cite id="CITEREFFujimoto1990" class="citation cs2">Fujimoto, Richard M. (October 1990), <a rel="nofollow" class="external text" href="http://www.lib.ncsu.edu/resolver/1840.4/7595">"Parallel discrete event simulation"</a>, <i><a href="Communications_of_the_ACM" title="Communications of the ACM">Communications of the ACM</a></i>, <b>33</b> (10): <span class="nowrap">30–</span>53, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F84537.84545">10.1145/84537.84545</a></span>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15054137">15054137</a></cite></li>

<li><cite id="CITEREFTanThng2000" class="citation cs2">Tan, Kah Leong; Thng, Li-Jin (2000), "SNOOPy Calendar Queue", <i>2000 Winter Simulation Conference Proceedings</i>, vol. 1, IEEE, pp. <span class="nowrap">487–</span>495, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fwsc.2000.899756">10.1109/wsc.2000.899756</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7803-6579-8</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2982776">2982776</a></cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-03-01" href="https://en.wikipedia.org/wiki/?title=Calendar_queue&oldid=1278349479">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>